home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / database / hl / hl-1.002 / hl-1 / Lib / PTree.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-14  |  4.2 KB  |  145 lines
  1. /* -*- Mode: C -*- */
  2. /* PTree.cc - PTree implementation code
  3.  * Created by Robert Heller on Thu Feb 27 20:34:01 1992
  4.  *
  5.  * ------------------------------------------------------------------
  6.  * Home Libarian by Deepwoods Software
  7.  * Common Class library implementation code
  8.  * ------------------------------------------------------------------
  9.  * Modification History:
  10.  * ------------------------------------------------------------------
  11.  * Contents:
  12.  * ------------------------------------------------------------------
  13.  * 
  14.  * 
  15.  * Copyright (c) 1991,1992 by Robert heller (D/B/A Deepwoods Software)
  16.  *        All Rights Reserved
  17.  * 
  18.  */
  19.  
  20. #include <PTree.h>
  21. int Node::numblocks;    // current number of allocated blocks
  22. Node* Node::blocks[maxblocks]; // allocated nodes
  23. Node* Node::freelist;    // linked list of available nodes
  24.  
  25. int Tree::numblocks;    // current number of allocated blocks
  26. Tree* Tree::blocks[maxblocks]; // allocated trees
  27. Tree* Tree::freelist;    // linked list of available trees
  28.  
  29. // default prototypical tree and node
  30. Tree defTree;
  31. Node defNode;
  32.  
  33. // Helper function to allocate an additional block of 100 Nodes
  34. void Node::moreblocks ()
  35. {
  36.     // Have we run out of blocks?
  37.     if (numblocks < maxblocks) {
  38.         // if not...  bump block counter
  39.         int iblock = numblocks++;
  40.         // snarf some memory
  41.         Node* p = blocks[iblock] = (Node*) new char[sizeof(Node)*blocksize];
  42.         // build linked list.  value field doubles as next pointer.
  43.         for (int ic = 1; ic < blocksize; ic++) {
  44.             p->value._string = (char*) (p+1);
  45.             p++;
  46.         }
  47.         // point last tail at current freelist
  48.         p->value._string = (char*) freelist;
  49.         // and set freelist head to first Node in fresh block
  50.         freelist = blocks[iblock];
  51.     }
  52. }
  53.             
  54. // Helper function to allocate an additional block of 100 Trees
  55. void Tree::moreblocks ()
  56. {
  57.     // Have we run out of blocks?
  58.     if (numblocks < maxblocks) {
  59.         // if not...  bump block counter
  60.         int iblock = numblocks++;
  61.         // snarf some memory
  62.         Tree* p = blocks[iblock] = (Tree*) new char[sizeof(Tree)*blocksize];
  63.         // build linked list.  left field doubles as next pointer.
  64.         for (int ic = 1; ic < blocksize; ic++) {
  65.             p->left = (Node*) (p+1);
  66.             p++;
  67.         }
  68.         // point last tail at current freelist
  69.         p->left = (Node*) freelist;
  70.         // and set freelist head to first Tree in fresh block
  71.         freelist = blocks[iblock];
  72.     }
  73. }
  74.             
  75. // overloaded new operator for Nodes
  76. void* Node::operator new (long bytes)
  77. {
  78.     // if freelist is empty, get more memory
  79.     if (defNode.freelist == 0) defNode.moreblocks();
  80.     // if freelist is still empty, return null
  81.     if (defNode.freelist == 0) return(0);
  82.     // get pointer to head of list
  83.     Node* newcard = defNode.freelist;
  84.     // set freelist to next card in the list
  85.     defNode.freelist = (Node*) newcard->value._string;
  86.     // unlink new card from the list
  87.     newcard->value._string = 0;
  88.     // retun new card
  89.     return(newcard);
  90. }
  91.  
  92. // overloaded delete operator for Nodes
  93. void Node::operator delete(void* vptr)
  94. {
  95.     // convert pointer to a Node*
  96.     Node* ptr = (Node*) vptr;
  97.     // if a null pointer, just return
  98.     if (ptr == 0) return;
  99.     // has this Node already be freed?
  100.     for (Node* p = defNode.freelist; p != 0; p = (Node*) p->value._string) {
  101.         if (p == ptr) return;    // if so, don't free it again
  102.     }
  103.     // link onto head of free list
  104.     ptr->value._string = (char*) defNode.freelist;
  105.     defNode.freelist = ptr;
  106. }
  107.  
  108.  
  109. // overloaded new operator for Trees
  110. void* Tree::operator new (long bytes)
  111. {
  112.     // if freelist is empty, get more memory
  113.     if (defTree.freelist == 0) defTree.moreblocks();
  114.     // if freelist is still empty, return null
  115.     if (defTree.freelist == 0) return(0);
  116.     // get pointer to head of list
  117.     Tree* newtree = defTree.freelist;
  118.     // set freelist to next Tree in the list
  119.     defTree.freelist = (Tree*) newtree->left;
  120.     // unlink new Tree from the list
  121.     newtree->left = 0;
  122.     // retun new Tree
  123.     return(newtree);
  124. }
  125.  
  126. // overloaded delete operator for Trees
  127. void Tree::operator delete(void* vptr)
  128. {
  129.     // convert pointer to a Tree*
  130.     Tree* ptr = (Tree*) vptr;
  131.     // if a null pointer, just return
  132.     if (ptr == 0) return;
  133.     // has this Tree already be freed?
  134.     for (Tree* p = defTree.freelist; p != 0; p = (Tree*) p->left) {
  135.         if (p == ptr) return;    // if so, don't free it again
  136.     }
  137.     // link onto head of free list
  138.     ptr->left = (Node*) defTree.freelist;
  139.     defTree.freelist = ptr;
  140. }
  141.  
  142.  
  143.  
  144.  
  145.